#ifndef BSTREE_H_
#define BSTREE_H_

template<typename K,typename V>
class treenode
{
public:
	typedef treenode<K,V>* pointer;
	K key;
	V value;
	pointer parent;
	pointer lchild;
	pointer rchild;
	int height;
	int depth;

public:
	treenode(K k,V v) :key(k),value(v),parent(nullptr), lchild(nullptr), rchild(nullptr), height(-1), depth(0)
	{}
	
	treenode(K k, V v, pointer p, pointer l, pointer r) :key(k), value(v), parent(p), lchild(l), rchild(r)
	{
		height = 0;
		depth = 0;
	}

	//bool operator!=(const treenode& node)
	//{
	//	return key != node.key;
	//}
	//bool operator==(const treenode& node)
	//{
	//	return key == node.key;
	//}
	//bool operator<(const treenode& node)
	//{
	//	return key < node.key;
	//}
	//bool operator>(const treenode& node)
	//{
	//	return key>node.key;
	//}

	bool isRchild()
	{
		if (parent == nullptr)
		{
			cout << "this is root node" << endl;
			return false;
		}
		if (parent->rchild == this)
			return true;
		else
			return false;
	}

	bool isLchild()
	{
		if (parent == nullptr)
		{
			cout << "this is root node" << endl;
			return false;
		}
		if (parent->lchild == this)
			return true;
		else
			return false;
	}

	pointer next()
	{
		if (parent == nullptr && rchild == nullptr)
		{
			return rchild;
		}
		else if (parent == nullptr && rchild != nullptr)
		{
			pointer temp = rchild;
			while (true)
			{
				if (temp->lchild == nullptr)
					break;
				temp = temp->lchild;
			}
			return temp;
		}
		else if (rchild != nullptr)
		{
			return rchild;
		}
		else if (isLchild())
		{
			return parent;
		}
		else if (isRchild())
		{

			pointer temp = parent;
			while (true)
			{
				if (temp == nullptr)
					return temp;
				if (temp->isLchild())
					break;
				temp = temp->parent;
			}
			return temp->parent;
		}
		else
			return nullptr;
	}

	pointer pre()
	{
		if (parent == nullptr && lchild == nullptr)
		{
			return lchild;
		}
		else if (parent == nullptr && lchild != nullptr)
		{
			pointer temp = lchild;
			while (true)
			{
				if (temp->rchild == nullptr)
					break;
				else
					temp = temp->rchild;
			}
			return temp;
		}
		else if (lchild != nullptr)
		{
			pointer temp = lchild;
			while (true)
			{
				if (temp->rchild == nullptr)
					break;
				else
					temp = temp->rchild;
			}
			return temp;
		}
		else if (lchild == nullptr && isRchild())
		{
			return parent;
		}
		else
		{
			pointer temp = parent;
			while (true)
			{
				if (temp->isRchild())
					break;
				else
					temp = temp->parent;
			}
			return temp->parent;
		}
	}

	int heightUpdate()
	{
		if (lchild == nullptr && rchild == nullptr)
		{
			return height = 0;
		}
		else if (lchild == nullptr && rchild != nullptr)
		{
			return height = rchild->height + 1;
		}
		else if (rchild == nullptr && lchild != nullptr)
		{
			return height = lchild->height + 1;
		}
		else
		{
			return height = max(lchild->height, rchild->height) + 1;
		}

	}

	void heightAbove()
	{
		pointer temp = this;
		while (temp != nullptr)
		{
			temp->heightUpdate();
			temp = temp->parent;
		}
	}

	int depthUpdate()
	{
		if (parent == nullptr)
		{
			return depth = 0;
		}
		return depth = parent->depth + 1;
	}

	void depthBelow()
	{

		if (lchild != nullptr)
		{
			lchild->depthUpdate();
		}
		if (rchild != nullptr)
		{
			rchild->depthUpdate();
		}
		if (lchild == nullptr && rchild == nullptr)
		{
			return;
		}
		if (lchild != nullptr)
		{
			lchild->depthBelow();
		}
		if (rchild != nullptr)
		{
			rchild->depthBelow();
		}
	}

	static int max(int x, int y)
	{
		if (x > y)
			return x;
		else
			return y;
	}
};

template<typename K,typename V>
class bstree_iterator :public iterator<bidirectional_iterator_tag, treenode<K, V>, ptrdiff_t, treenode<K, V>*, treenode<K, V>&>
{
public:
	typedef treenode<K, V> node_type;
	typedef bstree_iterator<K, V> iterator;
	pointer node;
	bstree_iterator(pointer x = nullptr) :node(x){}
	bstree_iterator(const iterator & x) :node(x.node){}

	reference operator*()const
	{
		return *node;
	}
	bool operator !=(const iterator &x)
	{
		if ((x.node) == nullptr && node == nullptr)
			return false;
		else if (x.node == nullptr || node != nullptr)
			return true;
		else if (x.node != nullptr || node == nullptr)
			return true;
		else 
			return (node->key) != ((x.node)->key);
	}
	iterator& operator++()
	{
		node = (pointer)(node->next());
		return *this;
	}
	iterator& operator--()
	{
		node = (pointer)(node->pre);
		return *this;
	}
	iterator& operator++(int)
	{
		iterator temp = *this;
		++(*this);
		return temp;
	}
	iterator& operator--(int)
	{
		iterator temp = *this;
		--(*this);
		return temp;
	}
	pointer operator->()const
	{
		return node;
	}

};
template<typename K,typename V>
class bstree
{
public:
	typedef typename bstree_iterator<K, V>::pointer		pointer;
	typedef typename bstree_iterator<K, V>::iterator	iterator;


public:
	pointer root;
	int count;

	bstree() :root(nullptr), count(0)
	{}

	bstree(K k, V v)
	{
		root = new treenode<K, V>(k, v);
		++count;
		root->height = 0;
		root->depth = 0;
	}
	
	pointer search(K k)
	{
		pointer temp = root;
		while (true)
		{
			pointer ptemp = temp;
			if ((temp->key) == k)
				return temp;
			else if ((temp->key) > k)
			{
				ptemp = temp;
				temp = temp->lchild;
			}
			else if ((temp->key) < k)
			{
				ptemp = temp;
				temp = temp->rchild;
			}
				
			
			if (temp == nullptr)
			{
				cout << "there is not node whose key is "<<k<< endl;
				return ptemp;
			}

		}
	}
	
	void insert(K k, V v)
	{
		pointer node = new treenode<K, V>(k, v);

		pointer temp = search(k);

		if (temp->key == k)
		{
			cout << "the key is exist" << endl;
			delete node;
			return;
		}
		else if (temp->key > k)
		{
			node->parent = temp;
			temp->lchild = node;
			temp->depthBelow();
			node->heightAbove();
		}
		else
		{
			node->parent = temp;
			temp->rchild = node;
			temp->depthBelow();
			node->heightAbove();
		}
	}

	iterator begin()
	{
		pointer temp = findMin(root);
		return iterator(temp);
	}
	iterator end()
	{
		pointer temp = findMax(root);
		return iterator(temp->rchild);
	}
	
	void remove(K k)
	{
		auto temp = search(k);
		if (temp->key != k)
		{
			cout << "the key does not exist" << endl;
			return;
		}
		if (hasLchild(temp) && hasRchild(temp))
		{
			remove_dchild(temp);
		}
		else if (hasRchild(temp) && !hasLchild(temp))
		{
			remove_right(temp);
		}
		else if (!hasRchild(temp) && hasLchild(temp))
		{
			remove_left(temp);
		}
		else
		{
			remove_leaf(temp);
		}
	}
	
	void remove_left(pointer node)
	{
		pointer & ptemp = node->parent;
		pointer & ltemp = node->lchild;
		if (ptemp->lchild == node)
		{
			ptemp->lchild = ltemp;
		}
		else
		{
			ptemp->rchild = ltemp;
		}
		ptemp->depthBelow();
		ltemp->heightAbove();
		delete node;
		node = nullptr;
	}
	
	void remove_right(pointer node)
	{
		pointer & ptemp = node->parent;
		pointer & rtemp = node->rchild;
		if (ptemp->rchild == node)
		{
			ptemp->rchild = rtemp;
		}
		else
		{
			ptemp->lchild = rtemp;
		}
		rtemp->parent = ptemp;

		rtemp->heightAbove();
		ptemp->depthBelow();

		delete node;
		node = nullptr;
	}
	
	void remove_leaf(pointer node)
	{
		pointer & ptemp = node->parent;
		if (ptemp->lchild == node)
		{
			ptemp->lchild = nullptr;
			if (ptemp->rchild == nullptr)
			{
				ptemp->height = 0;
			}
			ptemp->heightAbove();
		}
		else
		{
			ptemp->rchild = nullptr;
			if (ptemp->lchild == nullptr)
			{
				ptemp->height = 0;
			}
			ptemp->heightAbove();
		}
	}
	
	void remove_dchild(pointer node)
	{
		pointer  ptemp = node->parent;
		pointer  ltemp = node->lchild;
		pointer  rtemp = node->rchild;
		pointer temp=findMin(rtemp);
		pointer temp_p = temp->parent;

		if (node == root)
		{

		}

		if (temp->rchild != nullptr)
		{
			pointer temp_r = temp->rchild;
			temp_p->lchild = temp_r;
			temp_r->parent = temp_p;
			
		}
		else
		{
			temp_p->lchild = nullptr;
		}
		
		
		temp->parent = ptemp;
		if (ptemp == nullptr)
		{
			root = temp;
		}
		else if (ptemp->rchild == node)
		{
			ptemp->rchild = temp;
		}
		else
		{
			ptemp->lchild = temp;
		}
		temp->lchild = ltemp;
		ltemp->parent = temp;
		if (rtemp == temp)
		{
			rtemp = nullptr;
		}
		temp->rchild = rtemp;
		rtemp->parent = temp;
		if (ptemp == nullptr)
		{
			temp->depth = 0;
			root = temp;
		}
		temp_p->heightAbove();
		temp->depthBelow();
		delete node;
		node = nullptr;
	}

	pointer findMin(pointer node)
	{
		while (true)
		{
			if (node->lchild == nullptr)
				break;
			node = node->lchild;
		}
		return node;
	}
	pointer findMax(pointer node)
	{
		while (true)
		{
			if (node->rchild == nullptr)
				break;
			node = node->rchild;
		}
		return node;
	}
	void show()
	{
		for (auto temp = begin(); temp != end();++temp)
		{
			cout<<(*temp).key<<"----"<<(*temp).value<<endl;
			
		}

	}

	static bool hasRchild(pointer node)
	{
		if (node->rchild != nullptr)
			return true;
		else
			return false;
	}

	static bool hasLchild(pointer node)
	{
		if (node->lchild != nullptr)
			return true;
		else
			return false;
	}

};
#endif